백준 2150번
오늘 풀어본 문제는 백준의 2150번 문제1이다. 문제 풀이에 사용한 언어는 C++ 이다.
solved.ac 기준 CLASS
문제 정보
이 문제의 내용과 조건은 다음과 같다.
문제
방향 그래프가 주어졌을 때, 그 그래프를 SCC들로 나누는 프로그램을 작성하시오.
방향 그래프의 SCC는 우선 정점의 최대 부분집합이며, 그 부분집합에 들어있는 서로 다른 임의의 두 정점 $u$, $v$에 대해서 $u$에서 $v$로 가는 경로와 $v$에서 $u$로 가는 경로가 모두 존재하는 경우를 말한다.
예를 들어 위와 같은 그림을 보자. 이 그래프에서 SCC들은 ${a, b, e}$, ${c, d}$, ${f, g}$, ${h}$ 가 있다. 물론 $h$에서 $h$로 가는 간선이 없는 경우에도 ${h}$는 SCC를 이룬다.
입력
첫째 줄에 두 정수 $V$ $(1 \leq V \leq 10,000)$, $E$ $(1 \leq E \leq 100,000)$가 주어진다. 이는 그래프가 $V$개의 정점과 $E$개의 간선으로 이루어져 있다는 의미이다. 다음 $E$개의 줄에는 간선에 대한 정보를 나타내는 두 정수 $A$, $B$가 주어진다. 이는 $A$번 정점과 $B$번 정점이 연결되어 있다는 의미이다.이때 방향은 $A \to B$가 된다.
정점은 $1$부터 $V$까지 번호가 매겨져 있다.
출력
첫째 줄에 SCC의 개수 $K$를 출력한다. 다음 $K$개의 줄에는 각 줄에 하나의 SCC에 속한 정점의 번호를 출력한다. 각 줄의 끝에는 $-1$을 출력하여 그 줄의 끝을 나타낸다. 각각의 SCC를 출력할 때 그 안에 속한 정점들은 오름차순으로 출력한다. 또한 여러 개의 SCC에 대해서는 그 안에 속해있는 가장 작은 정점의 정점 번호 순으로 출력한다.
풀이과정
첫 번째 시도
이 문제는 Tarjan 알고리즘이라는 것을 이용해서 풀어야 하는 문제이다. Tarjan 알고리즘은 SCC 들을 찾아내는 알고리즘으로, 내용이 복잡하고 길기 때문에 간단하게만 설명하도록 하겠다.
Tarjan 알고리즘은 DFS Tree를 이용하여 각 노드가 방문되는 순서를 기록하고, 어떤 노드를 중심으로 한 subtree가 그 노드의 조상에 도달할 수 있는지 없는지를 확인하여 SCC를 확인한다.
도달할 수 있다면, SCC의 정의에 의해서 더 많은 노드들이 포함되어야 하는 것이고, 도달할 수 있는 한계가 조사를 시작한 노드까지라면, 그 만큼이 SCC인 것이다.
그리고 문제를 푸는 과정에서 SCC들을 정렬해야 했는데, SCC 자체적으로도 정렬을 해야하고, SCC 끼리도 정렬을 해야했다. 요즘 정렬 문제만 나오면 냅다 std::priority_queue 를 사용하는 버릇이 있었고, 그 결과 std::priority_queue 안에 std::priority_queue 를 넣는 웃긴 결과가 나오게 되었다.
코드는 다음과 같이 작성하였다.
#include <bits/stdc++.h>
using namespace std;
bool alreadyInGroup[10001] = { 0, };
int orderOfFound[10001] = { 0, };
int highestReachable[10001] = { 0, };
int numberOfGroup[10001] = { 0, };
int tempOrder = 1;
int numberOfSCCs = 0;
vector<vector<int>> graph(10001);
stack<int> s;
vector<priority_queue<int, vector<int>, greater<int>>> SCCs(10001);
struct cmp {
bool operator()(const priority_queue<int, vector<int>, greater<int>>& q1, const priority_queue<int, vector<int>, greater<int>>& q2) {
return q1.top() > q2.top();
}
};
priority_queue< priority_queue<int, vector<int>, greater<int>>, vector<priority_queue<int, vector<int>, greater<int>>>, cmp> orderedSCCs;
void tarjan(int nodeToCheck);
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int V, E, A, B;
cin >> V >> E;
for (int i = 0; i < E; i++) {
cin >> A >> B;
graph[A].emplace_back(B);
}
tarjan(1);
cout << numberOfSCCs << "\n";
for (int i = 0; i < numberOfSCCs; i++) {
orderedSCCs.push(SCCs[i]);
}
for (int i = 0; i < numberOfSCCs; i++) {
auto currentSCC = orderedSCCs.top();
while (!currentSCC.empty()) {
cout << currentSCC.top() << " ";
currentSCC.pop();
}
cout << -1 << "\n";
orderedSCCs.pop();
}
return 0;
}
void tarjan(int nodeToCheck) {
orderOfFound[nodeToCheck] = highestReachable[nodeToCheck] = tempOrder;
tempOrder++;
s.push(nodeToCheck);
for (auto i : graph[nodeToCheck]) {
if (orderOfFound[i] == 0) {
tarjan(i);
highestReachable[nodeToCheck] = min(highestReachable[nodeToCheck], highestReachable[i]);
}
else if (alreadyInGroup[i] == false) {
highestReachable[nodeToCheck] = min(highestReachable[nodeToCheck], orderOfFound[i]);
}
}
if (highestReachable[nodeToCheck] == orderOfFound[nodeToCheck]) {
while (s.top() != nodeToCheck) {
int currentNode = s.top();
s.pop();
alreadyInGroup[currentNode] = true;
SCCs[numberOfSCCs].push(currentNode);
numberOfGroup[currentNode] = numberOfSCCs;
}
int highestInSCC = s.top();
s.pop();
alreadyInGroup[highestInSCC] = 1;
SCCs[numberOfSCCs].push(highestInSCC);
numberOfGroup[highestInSCC] = numberOfSCCs;
numberOfSCCs++;
}
}
실행 결과, 틀렸습니다 가 떴다.
두 번째 시도
문제가 되었던 부분은 한 노드에서 대해서만 탐색을 진행했기 때문에 다른 노드들의 SCC를 확인하지 못한 부분이었다. 그래서 for 문을 이용하여 DFS Tree로 탐색하는 과정에서 발견되지 않은 노드들에 대해 탐색을 진행하도록 코드를 수정하였다.
코드는 다음과 같이 작성하였다.
#include <bits/stdc++.h>
using namespace std;
bool alreadyInGroup[10001] = { 0, };
int orderOfFound[10001] = { 0, };
int highestReachable[10001] = { 0, };
int numberOfGroup[10001] = { 0, };
int tempOrder = 1;
int numberOfSCCs = 0;
vector<vector<int>> graph(10001);
stack<int> s;
vector<priority_queue<int, vector<int>, greater<int>>> SCCs(10001);
struct cmp {
bool operator()(const priority_queue<int, vector<int>, greater<int>>& q1, const priority_queue<int, vector<int>, greater<int>>& q2) {
return q1.top() > q2.top();
}
};
priority_queue< priority_queue<int, vector<int>, greater<int>>, vector<priority_queue<int, vector<int>, greater<int>>>, cmp> orderedSCCs;
void tarjan(int nodeToCheck);
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int V, E, A, B;
cin >> V >> E;
for (int i = 0; i < E; i++) {
cin >> A >> B;
graph[A].emplace_back(B);
}
for (int i = 1; i <= V; i++) {
if (orderOfFound[i] == 0) {
tarjan(i);
}
}
cout << numberOfSCCs << "\n";
for (int i = 0; i < numberOfSCCs; i++) {
orderedSCCs.push(SCCs[i]);
}
for (int i = 0; i < numberOfSCCs; i++) {
auto currentSCC = orderedSCCs.top();
while (!currentSCC.empty()) {
cout << currentSCC.top() << " ";
currentSCC.pop();
}
cout << -1 << "\n";
orderedSCCs.pop();
}
return 0;
}
void tarjan(int nodeToCheck) {
orderOfFound[nodeToCheck] = highestReachable[nodeToCheck] = tempOrder;
tempOrder++;
s.push(nodeToCheck);
for (auto i : graph[nodeToCheck]) {
if (orderOfFound[i] == 0) {
tarjan(i);
highestReachable[nodeToCheck] = min(highestReachable[nodeToCheck], highestReachable[i]);
}
else if (alreadyInGroup[i] == false) {
highestReachable[nodeToCheck] = min(highestReachable[nodeToCheck], orderOfFound[i]);
}
}
if (highestReachable[nodeToCheck] == orderOfFound[nodeToCheck]) {
while (s.top() != nodeToCheck) {
int currentNode = s.top();
s.pop();
alreadyInGroup[currentNode] = true;
SCCs[numberOfSCCs].push(currentNode);
numberOfGroup[currentNode] = numberOfSCCs;
}
int highestInSCC = s.top();
s.pop();
alreadyInGroup[highestInSCC] = 1;
SCCs[numberOfSCCs].push(highestInSCC);
numberOfGroup[highestInSCC] = numberOfSCCs;
numberOfSCCs++;
}
}
그러자 모든 테스트 케이스를 통과하고 정답이 나오는 것을 확인할 수 있었다.
마무리
CLASS 6의 문제는 역시 엄청 어려운 것 같다. 항상 접하는 문제마다 새로운 유형인 느낌이고, 알아야 할 내용들도 많으며, 이론을 코드로 구현하는 것도 꽤 어려운 문제인 것 같다.
물론 이건 내가 CLASS 6의 문제들을 아직 많이 풀어보지 않았기 때문도 있지만, 내가 아직 PS에 대한 지식과 실력이 부족한 점이 큰 것 같다. 더 열심히 하지 않으면 안되겠다는 생각이 든다.
오늘의 PS는 여기까지!
1: https://www.acmicpc.net/problem/2150